Критерий эйлерова графа

Граф без изолированных вершин является эйлеровым тогда и только тогда, когда он связен и степени всех его вершин четны.

$\Large{\implies}$ Пусть $G$ — эйлеров граф без изолированных вершин. Это означает, что каждая вершина инцидентна хотя бы одному ребру. Эйлеров цикл проходит по всем вершинам, поэтому любые две вершины в $G$ соединены цепью, являющейся частью эйлерова цикла. Следовательно, граф $G$ связен. Рассмотрим произвольную вершину $v$. При обходе по эйлерову циклу мы "заходим" в вершину $v$ столько же раз, сколько "выходим" из нее. Каждое инцидентное $v$ ребро используется либо для захода, либо для выхода. Петля используется и для захода, и для выхода, и при подсчете степени вершины она учитывается дважды. Остальные ребра разбиваются на пары: входящее ребро и исходящее ребро. Следовательно, степень вершины $v$ четна. $\Large{\impliedby}$ Пусть $G$ связен, и степени всех его вершин четны. Построим в $G$ эйлеров цикл. Если в $G$ есть петли, их можно временно удалить (это не нарушит связность графа и четность степеней вершин), построить эйлеров цикл в получившемся графе, а затем встроить петли обратно в построенный цикл, получая эйлеров цикл в исходном графе $G$. Поэтому в дальнейшем считаем, что в $G$ нет петель. Выберем произвольную вершину $v_0$. Так как $G$ связен и не имеет изолированных вершин, $\deg(v_0) > 0$. Начнем строить цепь из $v_0$, на каждом шаге произвольно выбирая ребро. Процесс остановится, когда цепь нельзя будет продолжить, то есть все ребра, инцидентные текущей вершине, уже будут включены в цепь. Так как число ребер в графе конечно, это произойдет через конечное число шагов. Пусть построена цепь $v_0, e_1, v_1, e_2, \ldots, e_k, v_k$. Докажем, что $v_k = v_0$, то есть мы построили цикл. Предположим противное: $v_k \neq v_0$. Для любой промежуточной вершины $v_l$ ($0 < l < k$) мы один раз вошли в нее и один раз вышли, использовав два ребра. В конечную вершину $v_k$ мы вошли некоторое число раз, а вышли на один раз меньше, использовав нечетное число инцидентных ей ребер. Но по условию $\deg(v_k)$ четна, значит, в $v_k$ есть еще хотя бы одно неиспользованное ребро. Это противоречит правилу построения цепи (мы остановились, когда ее нельзя было продолжить). Следовательно, $v_k = v_0$. Итак, мы построили цикл $C_1 = (v_0, e_1, \ldots, e_k, v_0)$. Если $C_1$ — эйлеров, то построение закончено. Если $C_1$ не эйлеров, то в графе $G_1 = G - \{e_1, \ldots, e_k\}$ есть ребра. Так как $G$ связен, среди этих ребер найдется ребро $f_1$, инцидентное некоторой вершине $v_i$ цикла $C_1$. В графе $G_1$ степени всех вершин также четны, так как при удалении ребер цикла $C_1$ степени его вершин уменьшились на 2. Рассмотрим компоненту связности графа $G_1$, содержащую ребро $f_1$. В ней тем же способом можно построить цикл $\bar{C}_2$ из ребер $f_1, \ldots, f_m$, начинающийся и заканчивающийся в вершине $v_i$. Объединим циклы: последовательность ребер $e_1, \ldots, e_i, f_1, \ldots, f_m, e_{i+1}, \ldots, e_k$ образует новый цикл $C_2$, в котором ребер больше, чем в $C_1$. Если $C_2$ эйлеров, построение закончено. В противном случае повторяем процедуру, расширяя цикл до $C_3$, и так далее. Поскольку число ребер в графе $G$ конечно, на каком-то шаге мы получим цикл $C_j$, который будет эйлеровым. $\square$